數位簽章演算法+橢圓曲線

基於離散對數的ELGamal算法有加上橢圓曲線的版本,那同鄉的數位簽章自然也不會少
1985年，Koblitz和Miller把數位簽章算法移植到橢圓曲線上,所以我們就有了ECDSA橢圓曲線數位簽章

如何使用

參數準備

首先都叫橢圓曲線了,當然要有個曲線阿,所有有了曲線EC

• 曲線最好不要自己生,能用已經有安全驗證的曲線
  很多曲線的database能用例如:https://neuromancer.sk/std/x962/prime256v1
• 接者在曲線上選一個G點,用現成曲線能用他給的,或自己選
  
• 還有G點的order:n,使得n⋅G=O,其中O為無窮遠點,而且n要是質數
• 在[1,2,...n-1]的範圍選一個私鑰d
• 在曲線上計算公鑰e=d⋅G(曲線上的運算都有mod p歐)
• 公開EC,G,e,n

簽章

• 將訊息pt經過hash成pt_hash(pt_hash只有最左邊的L位元會用到,而L為n的位元數)
• 在[1,2,...n-1]隨機且不重複選擇隨機秘密k
• 計算點k⋅G的x,y值為(x1,y1)
• 計算r=x1 mod n,如果r==0則重新選擇k
• 計算s=k^-1(pt_hash+rd) mod n,如果s==0則重新選擇k
• 簽章為(r,s)
• 簽章和訊息一起送出

驗章

• 檢查公鑰e在曲線上而且不是O
• 檢查n⋅e是O
• 檢查(r,s)在[1,2,...n-1]
• 將訊息pt經過hash成pt_hash
• 計算u1=pt_hash⋅s^-1 mod n和u2=r⋅s^-1 mod n
• 計算曲線上的點(x1,y1)=u1⋅G+u2⋅e,如果為無窮遠點則簽章失效
• 如果r=x1 mod n簽章有效,否則無效

注意

1.建議不要自己生曲線
2.隨機秘密k要保好,且不重複,不可預測(偽隨機)
3.隨機秘密k重複會私鑰洩漏(2010年的ps3)